
def max_heapify(A,i):
	l = 2 * i + 1
	r = 2 * i + 2
	largest = 0
	
	if l < len(A) & A[l] > A[i]:
		largest = l
		pass
	else:
		largest = i

	if r < len(A) & A[r] > A[largest]:
		largest = r
		pass
	if largest != i:
		temp = A[i]
		A[i] = A[largest]
		A[largest] = temp
		max_heapify(A, largest)
		pass

def build_max_heap(A):
	size = len(A)
	half_size = size/2
	for i in range(half_size,1,-1):
		print i
		max_heapify(A,i)

def heapsort(A):
	build_max_heap(A)
	size = len(A)
	for i in range((len(A)-1), 2, -1):
		tem = A[1]
		A[1] = A[i]
		A[i] =  temp
		sze = size -1
		max_heapify(A,1)

#A=[4,1,3,2,16,9,10,14,8,7]
A=[16,4,10,14,7,9,3,2,8,1]
#max_heapify(A,1)

#print A

heapsort(A)
print A